The present invention relates to a computer system for solving various scheduling problems, for example, a work scheduling system, and in particular, to a scheduling system suitably applicable to a case where constraints for the scheduling are frequently changed.
Heretofore, there have been developed various kinds of scheduling systems, and the scheduling methods employed therein can be classified into the following two kinds.
In the first scheduling method, a scheduling problem represented in a mathematical formulation is inputed to a computer system, which then solves the scheduling problem according to a mathematical programming method like that described, for example, in N. Saji et al., "OPERATIONS RESEARCH; 6-4 assignment problem", July 1963, pp. 225-229 and S. Tamano et al., "PRINT CIRCUIT BOARD DESIGN AIDING EXPERT SYSTEM", preprint for 33rd meeting of the Information Processing Society of Japan; 1986 (latter half), pp. 1165-1166.
On the other hand, in the second scheduling method, all know-how information items associated with the scheduling are entirely programmed so as to effect the scheduling through a computer simulation.
If all constraints for the scheduling can be determined in advance so as to clearly formulate the scheduling problem, it is possible to achieve the scheduling according to the conventional scheduling method. As described herebelow, however, in actual, the constraints for the scheduling cannot be easily determined in advance; furthermore, the problem itself changes in association with the circumferential environment. Consequently, few systems adopting the conventional method have been put to the practical use.
A. Difficulties associated with prior decision of scheduling constraints
In many cases, all schedule constraints cannot be determined prior to the scheduling, for example, in a scheduling of a production process, the scheduling is desirably required to be effected to reserve the maintenance time of an equipment to the possible extent; however, because of the production quantity and the relationship with respect to the maintenance time of other equipment, the actual scheduling is often to be achieved by changing a portion of the maintenance time of the equipment.
B. Change of problem itself in association with circumferential environment
The schedule problem varies due to changes in the environment; in consequence, the scheduling algorithm is also required to follow the change. In the conventional scheduling method, however, since the scheduling algorithm is coded in a program, it is practically impossible to arbitrarily modify the algorithm.
In order to solve the problems above, there has been proposed a system using a knowledge engineering technique in which know-how information items and constraints related to the scheduling are configured in a knowledge base so as to cope with the changes in the constraints, thereby solving the scheduling problem through a computer simulation. As an example of this system, there has been known, for example, the Printed Board Design Process Control Aid Expert System described in pages 1165 to 1166 of the Proceeding of 33rd National Conference of Information Processing Society of Japan. However, also in the system above, since the allocation is sequentially achieved by respectively paying attention to the maintenance jobs and the like associated with a work and an apparatus, the obtained schedule is not always satisfactorily balanced as a whole.
In addition, there have been beforehand determined the periods of time for the maintenance of a production apparatus and the like, it is difficult to decide the allocation of a point of time when the actual job is to be effected in such a period. To overcome the difficulty, according to the conventional method, the point of time when the maintenance job is to be conducted is determined through the trial and error. In such a situation, a considerably great period of time is required for the scheduling and the results of the scheduling is not necessarily satisfactory for the user.